import math
from collections import Counter

def euclidean_distance(x1, x2):
    """计算两个样本之间的欧氏距离"""
    return math.sqrt(sum([(a - b) **2 for a, b in zip(x1, x2)]))

def knn_predict(X_train, y_train, x_test, k=3):
    """
    单个样本的k近邻预测
    参数:
        X_train: 训练样本特征（列表，每个元素为样本的特征向量）
        y_train: 训练样本标签（列表，与X_train一一对应）
        x_test: 待预测的测试样本
        k: 近邻数量
    返回:
        预测标签
    """
    # 计算测试样本与所有训练样本的距离
    distances = []
    for i in range(len(X_train)):
        dist = euclidean_distance(x_test, X_train[i])
        distances.append((dist, y_train[i]))  # 存储（距离，标签）元组
    
    # 按距离升序排序，取前k个近邻
    distances.sort()
    k_neighbors = distances[:k]
    
    # 提取近邻的标签并投票（多数表决）
    k_labels = [label for (_, label) in k_neighbors]
    most_common = Counter(k_labels).most_common(1)  # 取出现次数最多的标签
    return most_common[0][0]

def knn_classify(X_train, y_train, X_test, k=3):
    """
    批量样本的k近邻分类
    参数:
        X_train: 训练样本特征
        y_train: 训练样本标签
        X_test: 测试样本特征（列表，每个元素为待预测样本）
        k: 近邻数量
    返回:
        预测标签列表（与X_test一一对应）
    """
    predictions = []
    for x in X_test:
        pred = knn_predict(X_train, y_train, x, k)
        predictions.append(pred)
    return predictions